import java.util.ArrayList;
import java.util.List;

/**
 * Created by zhourh on 2018/9/11.
 *
 * 报数序列是指一个整照其中的整数的顺序进数序列，按行报数，得到下一个数。其前五项如下：

 1.     1
 2.     11
 3.     21
 4.     1211
 5.     111221
 1 被读作  "one 1"  ("一个一") , 即 11。
 11 被读作 "two 1s" ("两个一"）, 即 21。
 21 被读作 "one 2",  "one 1" （"一个二" ,  "一个一") , 即 1211。

 给定一个正整数 n（1 ≤ n ≤ 30），输出报数序列的第 n 项。

 注意：整数顺序将表示为一个字符串。



 示例 1:

 输入: 1
 输出: "1"
 示例 2:

 输入: 4
 输出: "1211"

 */
public class CountAndSay {

    private static List<String> sayCounts;

    static {
        sayCounts = new ArrayList<>();
        sayCounts.add("1");
    }

    public static void main(String[] args) {
        System.out.println(new CountAndSay().countAndSay(5));
    }

    public String countAndSay(int n) {
        if (sayCounts.size() >= n) {
            return sayCounts.get(n - 1);
        }

        String lastSayCount = countAndSay(n - 1);

        StringBuilder say = new StringBuilder("");
        int targetChar = 0;
        int targetCount = 0;

        char[] chars = lastSayCount.toCharArray();
        for (char c : chars) {
            if (targetCount == 0) {
                targetChar = c;
                targetCount++;
            } else if (targetCount > 0 && targetChar == c) {
                targetCount++;
            } else if (targetCount > 0 && targetChar != c) {
                say.append(targetCount).append(targetChar - 48);
                targetCount = 1;
                targetChar = c;
            }
        }

        if (targetCount > 0) {
            say.append(targetCount).append(targetChar - 48);
        }

        String sayResult = say.toString();
        sayCounts.add(n - 1, sayResult);
        return sayResult;
    }
}
